package Leetcode.Dichotomy;

/**
 * @Author: kirito
 * @Date: 2024/4/3 16:50
 * @Description:
 * H 指数 II
 * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
 *
 * h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
 *
 * 请你设计并实现对数时间复杂度的算法解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：citations = [0,1,3,5,6]
 * 输出：3
 * 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
 *      由于研究者有3篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。
 * 示例 2：
 *
 * 输入：citations = [1,2,100]
 * 输出：2
 *
 *
 * 提示：
 *
 * n == citations.length
 * 1 <= n <= 105
 * 0 <= citations[i] <= 1000
 * citations 按 升序排列
 */

public class hIndex {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 7;
        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found");
        }
    }
    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, 0, arr.length - 1, target);
    }
    /**
     * 递归版本
     * @param arr   数组
     * @param low   起始
     * @param high  结束
     * @param target    寻找目标数字
     * @return  目标数字索引，找不到返回-1
     *
     * #include <stdio.h>
     *
     * int binarySearch(int arr[], int low, int high, int target) {
     *     if (low <= high) {
     *         int mid = low + (high - low) / 2;
     *
     *         if (arr[mid] == target) {
     *             return mid;
     *         }
     *
     *         if (arr[mid] < target) {
     *             return binarySearch(arr, mid + 1, high, target);
     *         }
     *
     *         return binarySearch(arr, low, mid - 1, target);
     *     }
     *
     *     return -1; // 元素不在数组中
     * }
     *
     * int main() {
     *     int arr[] = {1, 3, 5, 7, 9};
     *     int target = 7;
     *     int result = binarySearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);
     *
     *     if (result != -1) {
     *         printf("Element found at index: %d\n", result);
     *     } else {
     *         printf("Element not found\n");
     *     }
     *
     *     return 0;
     * }
     */
    private static int binarySearch(int[] arr, int low, int high, int target) {
        if (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] < target) {
                return binarySearch(arr, mid + 1, high, target);
            }

            return binarySearch(arr, low, mid - 1, target);
        }

        return -1; // 元素不在数组中
    }


    public static int hIndex(int[] citations) {
        // 在区间 [left, right] 内询问
        int n = citations.length;
        int left = 1;
        int right = n;
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // left-1 的回答一定为「是」
            // right+1 的回答一定为「否」
            int mid = (left + right) >>> 1;
            // 引用次数最多的 mid 篇论文，引用次数均 >= mid
            if (citations[n - mid] >= mid) {
                left = mid + 1; // 询问范围缩小到 [mid+1, right]
            } else {
                right = mid - 1; // 询问范围缩小到 [left, mid-1]
            }
        }
        // 循环结束后 right 等于 left-1，回答一定为「是」
        // 根据循环不变量，right 现在是最大的回答为「是」的数
        return right;
    }

    public static int hIndex2(int[] citations) {
        // 在区间 [left, right] 内询问
        int n = citations.length;
        int left = 1;
        int right = n+1;
        while (left < right) { // 区间不为空
            // 循环不变量：
            // left-1 的回答一定为「是」
            // right 的回答一定为「否」
            int mid = (left + right) >>> 1;
            // 引用次数最多的 mid 篇论文，引用次数均 >= mid
            if (citations[n - mid] >= mid) {
                left = mid + 1; // 询问范围缩小到 [mid+1, right]
            } else {
                right = mid; // 询问范围缩小到 [left, mid-1]
            }
        }
        // 循环结束后 right 等于 left-1，回答一定为「是」
        // 根据循环不变量，right 现在是最大的回答为「是」的数
        return left-1;
    }

    public int hIndex3(int[] citations) {
        // 在区间 (left, right] 内询问
        int n = citations.length;
        int left = 0;
        int right = n;
        while (left < right) { // 区间不为空
            // 循环不变量：
            // left 的回答一定为「是」
            // right+1 的回答一定为「否」
            int mid = (left + right + 1) >>> 1; // 保证 mid 在二分区间内
            // 引用次数最多的 mid 篇论文，引用次数均 >= mid
            if (citations[n - mid] >= mid) {
                left = mid; // 询问范围缩小到 (mid, right]
            } else {
                right = mid - 1; // 询问范围缩小到 (left, mid-1]
            }
        }
        // 根据循环不变量，left 现在是最大的回答为「是」的数
        return left;
    }

    public int hIndex4(int[] citations) {
        // 在区间 (left, right) 内询问
        int n = citations.length;
        int left = 0;
        int right = n + 1;
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // left 的回答一定为「是」
            // right 的回答一定为「否」
            int mid = (left + right) >>> 1;
            // 引用次数最多的 mid 篇论文，引用次数均 >= mid
            if (citations[n - mid] >= mid) {
                left = mid; // 询问范围缩小到 (mid, right)
            } else {
                right = mid; // 询问范围缩小到 (left, mid)
            }
        }
        // 根据循环不变量，left 现在是最大的回答为「是」的数
        return left;
    }

}
